package com.algorithm.learning.base.链表;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/20 21:26
 **/
public class 单链表实现队列和栈 {

    public static class Node<V> {
        private V value;
        private Node<V> next;

        public Node(V value) {
            this.value = value;
        }
    }

    /**
     * 链表实现单向队列
     * <p>
     * 队列：先进先出
     *
     * @param <V>
     */
    public static class MyQueue<V> {
        private Node<V> head;
        private Node<V> tail;

        // 队列大小
        private int size;

        public MyQueue() {
            this.head = null;
            this.tail = null;
            this.size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 存入数据
         *
         * @param value
         */
        public void offer(V value) {
            Node<V> node = new Node<>(value);
            if (head == null) {
                head = node;
                tail = node;
            } else {
                Node<V> last = tail;
                last.next = node;
                tail = node;
            }
            size++;
        }

        /**
         * 队列弹出第一个元素
         *
         * @return
         */
        public V poll() {
            V ans = null;
            if (head == null) {
                tail = null;
            } else {
                ans = head.value;
                head = head.next;
                size--;
            }
            return ans;
        }

        public V peek() {
            V ans = null;
            if (head == null) {
                tail = null;
            } else {
                return head.value;
            }
            return ans;
        }
    }

    public static class MyStack<V> {
        private Node<V> head;

        // 队列大小
        private int size;

        public MyStack() {
            this.head = null;
            this.size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public void push(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
            } else {
                cur.next = head;
                head = cur;
            }
            size++;
        }

        public V pop() {
            V ans = null;
            if (head != null) {
                ans = head.value;
                head = head.next;
                size--;
            }
            return ans;
        }

        public V peek() {
            V ans = null;
            if (head != null) {
                ans = head.value;
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue.peek());
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }


        MyStack<Integer> stack = new MyStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);

        System.out.println(stack.peek());
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
